package com.aqie.easy.bfs;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * 994  O(N) N: 二维方格数量 todo
 */
public class OrangesRotting {
    /**
     * 1, 6ms
     */
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};

    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length;

        // queue : all starting cells with rotten oranges
        Queue<Integer> queue = new ArrayDeque<>();
        Map<Integer, Integer> depth = new HashMap<>();
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                if (grid[r][c] == 2) {
                    int code = r * C + c;
                    queue.add(code);
                    depth.put(code, 0);
                }

        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / C, c = code % C;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);
                    ans = depth.get(ncode);
                }
            }
        }

        for (int[] row : grid)
            for (int v : row)
                if (v == 1)
                    return -1;
        return ans;

    }

    /**
     * 2, 4ms
     * @param grid
     * @return
     */
    public int orangesRotting2(int[][] grid) {
        int times = 1;
        boolean flag = true;
        int[][] note = new int[grid.length][grid[0].length];
        for(int i=0; i<note.length; i++){
            for(int j=0; j<note[0].length; j++){
                if(grid[i][j]==2){
                    note[i][j] = times;
                }else{
                    note[i][j] = 0;
                }
            }
        }
        while(flag){
            flag = false;
            for(int i=0; i<grid.length; i++){
                for(int j=0; j<grid[0].length; j++){
                    if(grid[i][j]==2&&note[i][j]==times){
                        if(i>0&&grid[i-1][j]==1){
                            grid[i-1][j] = 2;
                            note[i-1][j] = times+1;
                            flag = true;
                        }
                        if(i<grid.length-1&&grid[i+1][j]==1){
                            grid[i+1][j] = 2;
                            note[i+1][j] = times+1;
                            flag = true;
                        }
                        if(j>0&&grid[i][j-1]==1){
                            grid[i][j-1] = 2;
                            note[i][j-1] = times+1;
                            flag = true;
                        }
                        if(j<grid[i].length-1&&grid[i][j+1]==1){
                            grid[i][j+1] = 2;
                            note[i][j+1] = times+1;
                            flag = true;
                        }
                    }
                }
            }
            if(flag){
                times++;;
            }
        }
        for (int[] aGrid : grid) {
            for (int j = 0; j < grid[0].length; j++) {
                if (aGrid[j] == 1) {
                    return -1;
                }
            }
        }
        return times-1;
    }
}


